/*  File Name	: Heap.cpp
 *  Author		: Javie Pong
 *	 E-mail		: 823960168@qq.com
 *  Created on	: 2012-5-12
 *  Description:
 */

#include "Heap.h"
#include <string.h>
#include <sys/time.h>
#include <iostream>
#include <stdlib.h>
Heap::Heap()
{
	this->heap_ = NULL;
	this->max_size_ = 0;
	this->cur_size_ = 0;
}

Heap::Heap(int size)
{
	this->heap_ = NULL;
	this->max_size_ = 0;
	this->cur_size_ = 0;
	size = size > 0 ? size : 2048;
	this->open(size);
}

Heap::~Heap()
{
	if(this->heap_!=NULL)
	{
		::free(this->heap_);
	}
}

int Heap::open(int size)
{
	size = size > 0 ? size : 2048;
	this->max_size_ = size;
	this->heap_ = new int64_t[size];
	memset(this->heap_,'0',this->max_size_*sizeof(int64_t));
	if(NULL==this->heap_)
	{
		return -1;
	}
	return 0;
}

int Heap::pop(int64_t &p)
{
	if(this->cur_size_<=0)
	{
		return -1;
	}
	p=this->heap_[0];
	this->heap_[0]= this->heap_[this->cur_size_-1];
	this->heap_[this->cur_size_-1] = 0;
	this->cur_size_--;
	this->sort();
	return 0;
}

int Heap::push(int64_t p)
{
	if(this->cur_size_ > this->max_size_)
	{
		return -1;
	}
	this->heap_[this->cur_size_] = p;
	this->sort();
	this->cur_size_++;
	return 0;
}


float Heap::timeval_msec_diff(const struct timeval *start, const struct timeval *end)
{
	float ms = end->tv_sec - start->tv_sec;
	ms *= 1000000;
	ms = (ms+(end->tv_usec - start->tv_usec)) / 1000.0000;
	return ms;

}

int Heap::sort(void)
{
//	timeval start;
//	gettimeofday(&start, 0);
	for(int i=this->cur_size_/2-1;i>=0;i--)
	{
		this->adjust(i,this->cur_size_);
	}
//	timeval end;
//	gettimeofday(&end, 0);
//	std::cout << std::endl<< "=1=="<< timeval_msec_diff(&start, &end) << "===" << std::endl;
	int tmp =0;

//	gettimeofday(&start, 0);
	for(int i=this->cur_size_-1;i>0;i--)
	{
		tmp = this->heap_[i];
		this->heap_[i] = this->heap_[0];
		this->heap_[0] = tmp;
		this->adjust(0,i);
	}
//	gettimeofday(&end, 0);
//	std::cout << std::endl<< "=2=="<< timeval_msec_diff(&start, &end) << "===" << std::endl;
	return 0;
}

using namespace std;
int Heap::adjust(int node,int len)
{
	int child = 2 * node + 1;
	int tmp = this->heap_[node];
	while ( child <=len)
	{
		if(child+1<len && this->heap_[child] < this->heap_[child+1])
		{
			child++;
		}
		if(this->heap_[child] > tmp)
		{
			//tmp = this->heap_[node];
			this->heap_[node]=this->heap_[child];

			node = child;
			child = 2*child +1;
		}
		else
		{
			break;
		}
	}
	this->heap_[node] = tmp;
//	int temp = this->heap_[node]; //记录
//	int parent = node;
//	int child = 2 * node + 1;
//	while (child <= len)
//	{
//		if (child < len && this->heap_[child] < this->heap_[child + 1])
//		{
//			child++;
//		}
//		if (heap_[child] > temp)
//		{
//			heap_[parent] = heap_[child];
//			parent = child;
//			child = 2 * child + 1;
//			continue;
//		}
//		else
//		{
//			break;
//		}
//	}
//	heap_[parent] = temp;
	return 0;
}
